package main

import "fmt"

//使用队列实现栈的下列操作：
//
//
// push(x) -- 元素 x 入栈
// pop() -- 移除栈顶元素
// top() -- 获取栈顶元素
// empty() -- 返回栈是否为空
//
//
// 注意:
//
//
// 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合
//法的。
// 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
// 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
//
// Related Topics 栈 设计
// 👍 257 👎 0

type Node struct {
	Val int
	Next *Node
}

type MyStack struct {
	Size int
	Head *Node
}


/** Initialize your data structure here. */
func Constructor() MyStack {
	return MyStack{
		Size: 0,
		Head: nil,
	}
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
	node := &Node{
		Val:  x,
		Next: nil,
	}

	if this.Head == nil {
		this.Head = node
	} else {
		node.Next = this.Head
		this.Head = node
	}

	this.Size++
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
	if this.Empty() {
		return -1
	}
	head := this.Head
	val := head.Val
	this.Head = this.Head.Next
	head = nil
	this.Size--
	return val
}


/** Get the top element. */
func (this *MyStack) Top() int {
	return this.Head.Val
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
	return this.Size == 0
}

func main() {
	/**
	 * Your MyStack object will be instantiated and called as such:
	 * obj := Constructor();
	 * obj.Push(x);
	 * param_2 := obj.Pop();
	 * param_3 := obj.Top();
	 * param_4 := obj.Empty();
	 */
	obj := Constructor()
	obj.Push(1)
	obj.Push(2)
	ret := obj.Pop()
	fmt.Println(ret)
	ret = obj.Top()
	fmt.Println(ret)
	fmt.Println(obj.Empty())
}
